#pragma once

namespace Tmpl {

template <typename TM>
class DataValuePoolPointers
{
public:
	
	void Init(int maxValues=4096)
	{
		mMaxValues = maxValues;
		mValues = MALLOC64(mMaxValues, TM*);
		mMappingTable = MALLOC64(mMaxValues, int);
		TM* values = new TM[mMaxValues];
		for (int i=0; i<mMaxValues; ++i)
		{
			mValues[i] = &values[i];
			mMappingTable[i] = -1;
		}
		mNextMapping = 0;
		mNextValue = 0;
	}

	void Destroy()
	{
		int v1 = 0;
		int v2 = 4096;
		while (v <= mMaxValues)
		{
			delete[] mValues[v1];
			v1 = v2;
			v *= 2;
		}
		FREE64(mValues);
		FREE64(mMappingTable);
		mMaxValues = 0;
		mMappingTable = 0;
		mNextMapping = 0;
		mValues = 0;
		mNextValue = 0;
	}

	void Clear()
	{
		for (int i=0; i<mMaxValues; ++i)
		{
			mMappingTable[i] = -1;
		}
		mNextMapping = 0;
		mNextValue = 0;
	}

	int NewValue()
	{
		// out of bounds, realloc
		if (mNextValue >= mMaxValues)
		{
			int newCount = mMaxValues;
			mMaxValues *= 2;
			mValues = REALLOC64(mValues, mMaxValues, TM*);
			mMappingTable = REALLOC64(mMappingTable, mMaxValues, int);
			assert(mMappingTable);
			assert(mValues);
			TM* values = new TM[mMaxValues];
			assert(values);
			for (int i=0; i<newCount; ++i)
			{
				int idx = i + newCount;
				mMappingTable[idx] = -1;
				mValues[idx] = &values[i];
			}
		}

		// return next
		while (mMappingTable[mNextMapping] > -1)
		{
			if (++mNextMapping >= mMaxValues)
			{
				mNextMapping = 0;
			}
		}
		mMappingTable[mNextMapping] = mNextValue++;
		return mNextMapping++;
	}

	void RemoveValue(int id)
	{
		assert((id >= 0 && id < mMaxValues));
		int mappedid = mMappingTable[id];
		assert((mappedid >= 0 && mappedid < mNextValue));

		// Only swap if the mappedid is not the last element
		if (mappedid < --mNextValue)
		{
			// Find the element in the mapping table
			int i=0;
			while (mMappingTable[i] != mNextValue){ ++i; }	
			mMappingTable[i] = mappedid;

			// swap last element with this one		
			TM** tmp = &mValues[mappedid];
			TM** a = &mValues[mappedid];
			TM** b = &mValues[mNextValue];
			*a = *b;
			*b = *tmp;
		}

		// Set the value to unmapped
		mMappingTable[id] = -1;
	}
	TM* GetValue(int id) const
	{
		assert((id >= 0 && id < mMaxValues));
		int mappedid = mMappingTable[id];
		assert((mappedid >= 0 && mappedid < mNextValue));
		return mValues[mappedid];
	}

	TM* GetUnmappedValue(int id)
	{
		return mValues[id];
	}
	TM** GetValueArray(){ return mValues; }
	int GetValueCount(){ return mNextValue; }
private:
	int mMaxValues;

	int mNextValue;
	TM** mValues;

	int mNextMapping;
	int* mMappingTable;
};


template <typename TM>
class DataValuePool
{
public:
	void Init(int maxValues=4096)
	{
		mMaxValues = maxValues;
		mValues = MALLOC64(mMaxValues, TM);
		mMappingTable = MALLOC64(mMaxValues, int);
		Clear();
	}

	void Destroy()
	{
		FREE64(mValues);
		FREE64(mMappingTable);
		mMaxValues = 0;
		mMappingTable = 0;
		mNextMapping = 0;
		mValues = 0;
		mNextValue = 0;
	}

	void Clear()
	{
		memset(mValues, 0, sizeof(TM) * mMaxValues);
		for (int i=0; i<mMaxValues; ++i) mMappingTable[i] = -1;
		mNextMapping = 0;
		mNextValue = 0;
	}

	int NewValue()
	{
		// out of bounds, realloc
		if (mNextValue >= mMaxValues)
		{
			mMaxValues *= 2;
			mValues = REALLOC64(mValues, mMaxValues, TM);
			mMappingTable = REALLOC64(mMappingTable, mMaxValues, int);
			for (int i=(mMaxValues >> 1); i<mMaxValues; ++i) mMappingTable[i] = -1;
		}

		// return next
		while (mMappingTable[mNextMapping] > -1)
		{
			if (++mNextMapping >= mMaxValues)
			{
				mNextMapping = 0;
			}
		}
		mMappingTable[mNextMapping] = mNextValue++;
		return mNextMapping++;
	}

	void RemoveValue(int id)
	{
		assert((id >= 0 && id < mMaxValues));
		int mappedid = mMappingTable[id];
		assert((mappedid >= 0 && mappedid < mNextValue));

		// Only swap if the mappedid is not the last element
		if (mappedid < --mNextValue)
		{
			// Find the element in the mapping table
			int i=0;
			while (mMappingTable[i] != mNextValue){ ++i; }	
			mMappingTable[i] = mappedid;

			// swap last element with this one
			mValues[mappedid] = mValues[mNextValue];
		}

		// Set the value to unmapped
		mMappingTable[id] = -1;
	}

	TM* GetValue(int id) const
	{
		assert((id >= 0 && id < mMaxValues));
		int mappedid = mMappingTable[id];
		assert((mappedid >= 0 && mappedid < mNextValue));
		return &mValues[mappedid];
	}

	TM* GetUnmappedValue(int id)
	{
		return &mValues[id];
	}
	TM* GetValueArray(){ return mValues; }
	int GetValueCount(){ return mNextValue; }
private:
	int mMaxValues;

	int mNextValue;
	TM* mValues;

	int mNextMapping;
	int* mMappingTable;
};

template <typename TM, typename TC> 
class DataValuePoolBuffered
{
public:
	void Init(int maxValues=4096)
	{
		mMaxValues = maxValues;
		mValues = MALLOC64(mMaxValues, TM);
		mLast = MALLOC64(mMaxValues, TC);
		mNext = MALLOC64(mMaxValues, TC);
		mMappingTable = MALLOC64(mMaxValues, int);
		Clear();
	}

	void Destroy()
	{
		FREE64(mValues);
		FREE64(mLast);
		FREE64(mNext);
		FREE64(mMappingTable);
	}

	void Clear()
	{
		memset(mValues, 0, sizeof(TM) * mMaxValues);
		memset(mLast, 0, sizeof(TC) * mMaxValues);
		memset(mNext, 0, sizeof(TC) * mMaxValues);
		for (int i=0; i<mMaxValues; ++i) mMappingTable[i] = -1;
		mNextMapping = 0;
		mNextValue = 0;
	}

	int NewValue()
	{
		// out of bounds, realloc
		if (mNextValue >= mMaxValues)
		{
			mMaxValues *= 2;
			mValues = REALLOC64(mValues, mMaxValues, TM);
			mLast = REALLOC64(mLast, mMaxValues, TC);
			mNext = REALLOC64(mNext, mMaxValues, TC);
			mMappingTable = REALLOC64(mMappingTable, mMaxValues, int);
			for (int i=(mMaxValues >> 1); i<mMaxValues; ++i) mMappingTable[i] = -1;
		}

		// return next
		while (mMappingTable[mNextMapping] > -1)
		{
			if (++mNextMapping >= mMaxValues)
			{
				mNextMapping = 0;
			}
		}
		mMappingTable[mNextMapping] = mNextValue++;
		return mNextMapping++;
	}

	void RemoveValue(int id)
	{
		assert((id >= 0 && id < mMaxValues));
		int mappedid = mMappingTable[id];
		assert((mappedid >= 0 && mappedid < mNextValue));

		// Only swap the mappedid is not the last element
		if (mappedid < --mNextValue)
		{
			// Find the element in the mapping table
			int i=0;
			while (mMappingTable[i] != mNextValue){ ++i; }	
			mMappingTable[i] = mappedid;

			// swap last element with this one
			mValues[mappedid] = mValues[mNextValue];
			mLast[mappedid] = mLast[mNextValue];
			mNext[mappedid] = mNext[mNextValue];
		}

		// Set the value to unmapped
		mMappingTable[id] = -1;
	}

	void CopyNextToLast()
	{
		memcpy(mLast, mNext, sizeof(TC) * mMaxValues);
	}

	TM* GetValue(int id)
	{
		assert((id >= 0 && id < mMaxValues));
		int mappedid = mMappingTable[id];
		assert((mappedid >= 0 && mappedid < mNextValue));
		return &mValues[mappedid];
	}

	TC* GetLast(int id)
	{
		assert((id >= 0 && id < mMaxValues));
		int mappedid = mMappingTable[id];
		assert((mappedid >= 0 && mappedid < mNextValue));
		return &mLast[mappedid];
	}

	TC* GetNext(int id)
	{
		assert((id >= 0 && id < mMaxValues));
		int mappedid = mMappingTable[id];
		assert((mappedid >= 0 && mappedid < mNextValue));
		return &mNext[mappedid];
	}
	TM* GetUnmappedValue(int id)
	{
		assert((id >= 0 && id < mNextValue));
		return &mValues[id];
	}

	TC* GetUnmappedLast(int id)
	{
		assert((id >= 0 && id < mNextValue));
		return &mLast[id];
	}

	TC* GetUnmappedNext(int id)
	{
		assert((id >= 0 && id < mNextValue));
		return &mNext[id];
	}


	TM* GetValueArray(){ return mValues; }
	int GetValueCount(){ return mNextValue; }

	TC* GetLastArray(){ return mLast; }
	TC* GetNextArray(){ return mNext; }

private:
	int mMaxValues;

	int mNextValue;
	TM* mValues;

	TC* mLast;
	TC* mNext;

	int mNextMapping;
	int* mMappingTable;
};

} // namespace Tmpl